package week09

// 22. 括号生成
// https://leetcode-cn.com/problems/generate-parentheses/

func generateParenthesis(n int) []string {
	return dfs(n, 0, []byte{}, []string{}, 0)
}

func dfs(max, index int, temp []byte, ans []string, count int) []string {
	if max*2 == index {
		if count == 0 {
			ans = append(ans, string(temp))
		}
		return ans
	}

	if count < max {
		count++
		temp = append(temp, '(')
		ans = dfs(max, index+1, temp, ans, count)
		temp = temp[:len(temp)-1]
		count--
	}

	if count > 0 {
		count--
		temp = append(temp, ')')
		ans = dfs(max, index+1, temp, ans, count)
		temp = temp[:len(temp)-1]
		count++
	}
	return ans
}